Known as a technology of effectively making use of a storage capacity of a storage device (storage) is a technology, called data overlap elimination, overlap exclusion and other equivalent nomenclatures, of not storing overlapped data in the storage device. The apparatus performing the data overlap elimination involves normally using Bloom filters and a multi-layer Bloom filter (refer to, e.g., Patent Documents 1, 2) for determining whether data are overlapped.
The Bloom filters and the multi-layer Bloom filter (which will hereinafter be generically termed the Bloom filter(s)) are each defined as a data structure disabled from acquiring a desired false-positive occurrence probability unless a size of the Bloom filter is set corresponding to a data count of management target data. Considering that the Bloom filter is management data used for determining whether an overlap exists, it follows that the technology of performing the overlap elimination is desired to have a large data reduction quantity (a total size of the data subjected to the overlap elimination by using the management data) per unit management data size.